package _11_整理题目._4_动态规划._模拟;

import org.junit.Test;

public class _29_正则表达式匹配 {
    
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
    
        boolean f[][] = new boolean[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                //分成空正则和非空正则两种
                if (j == 0) {
                    f[i][j] = i==0;
                } else {
                    //非空正则分为两种情况 * 和 非*
                    if (p.charAt(j-1) != '*') {
                        if (i>0 && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.')) {
                            f[i][j] = f[i-1][j-1];
                        }
                    } else {
                        //碰到 * 了，分为看和不看两种情况
                        //不看
                        if (j >= 2) {
                            f[i][j] |= f[i][j - 2];
                        }
                        //看
                        if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                            f[i][j] |= f[i - 1][j];
                        }
                    }
                }
            }
        }
        return f[m][n];
    }
    
    @Test
    public void main() {
        String str1 = "aaa";
        String str2 = "aa.*a";
        assert isMatch(str1, str2) == true;
    }
}
